83. 删除排序链表中的重复元素

Similar Question

leading to the advanced question

Solution Tips

方案一: 快慢指针

受到快慢指针原地删除的影响, 这题链表也使用了两个指针, 但是其实只需要一个指针就够了, 因为删除重复的元素, 只需要保留一个, slow 和 fast 永远是紧紧挨在一起的.

也可以理解为在链表中本身就包含了 node.next 这样一个指针, 所以只需要保留一个指针就 ok

但是快慢指针的方案, 可以灵活的处理保留 k 个重复数的场景

var deleteDuplicates = function(head) {
    if (head === null) return head;
    // 慢指针指向保留的元素, 快指针移动, 如果相同则删除
    // 如果不同则更新慢指针到快指针的位置
    // 需要保证 slow 总是在 fast 的前一个位置, 才能正确删除
    let slow = head;
    let fast = head.next;

    while (fast !== null) {
        if (slow.val === fast.val) {
            // 删除
            slow.next = fast.next; 
        }
        else {
            // 更新 slow
            slow = fast;
        }
        fast = fast.next;
    }

    return head;
};

var deleteDuplicates = function(head) {
    if (!head) {
        return head;
    }

    let cur = head;
    while (cur.next) {
        if (cur.val === cur.next.val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }
    return head;
};